package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/12/02 10:39
 */
public class _321_plus {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxNumber(new int[]{3, 4, 6, 5}, new int[]{9, 1, 2, 5, 8, 3}, 5)));
    }

    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        if (k == 0) return new int[0];
        int[] maxSub1 = new int[k];
        int[] maxSub2 = new int[k];
        int[] res = new int[k];
        //92583 96583 98653
        for (int l = 0; l <= Math.min(k, nums1.length); l++) {
            if (l + nums2.length < k) continue;
            maxSubArray(nums1, maxSub1, l);
            maxSubArray(nums2, maxSub2, k - l);
            res = merge(maxSub1, maxSub2, l, k - l, res);
        }
        return res;
    }

    private static void maxSubArray(int[] nums, int[] maxSub, int size) {
        if (size == 0) return;
        //得到当前部分的最大的数组
        for (int i = 0, j = 0; i < nums.length; i++) {
            while (j > 0 && nums.length - i + j > size && nums[i] > maxSub[j - 1])
                j--;
            if (j < size) maxSub[j++] = nums[i];
            //          System.out.println(maxSub[0] + " " + maxSub[1]);
        }
    }

    private static int[] merge(int[] maxSub1, int[] maxSub2, int size1, int size2, int[] res) {
        int[] merge = new int[res.length];
        int i = 0, j = 0, idx = 0;
        boolean equal = true;
        while (i < size1 || j < size2) {
            if (i >= size1) merge[idx] = maxSub2[j++];
            else if (j >= size2) merge[idx] = maxSub1[i++];
            else {
                int ii = i, jj = j;
                while (ii < size1 && jj < size2 && maxSub1[ii] == maxSub2[jj]) {
                    ii++;
                    jj++;
                }
                if (ii < size1 && jj < size2) {
                    if (maxSub1[ii] > maxSub2[jj]) merge[idx] = maxSub1[i++];
                    else merge[idx] = maxSub2[j++];
                } else if (ii == size1) {
                    merge[idx] = maxSub2[j++];
                } else {
                    merge[idx] = maxSub1[i++];
                }
            }

            if (merge[idx] > res[idx]) equal = false;
            else if (equal && merge[idx] < res[idx]) break;
            idx++;
        }

        int k = merge.length;
        if (!equal && i == size1 && j == size2) return merge;
        if (equal && merge[k - 1] > res[k - 1]) return merge;
        return res;
    }
}
